Section: New Results

Parallel graph remapping

Participants : Sébastien Fourestier, François Pellegrini [Corresponding member] .

Last year, a set of new algorithms for sequential remapping and mapping with fixed vertices has been devised. These algorithms had been intergrated in the Charm++ parallel environment, in the context of a collaboration with the Joint Laboratory for Petascale Computing (JLPC) between Inria and UIUC.

These algorithms have been integrated in version 6.0 of Scotch , which has been released in the beginning of December. This release also comprises new threaded formulations of the critical and most time-consuming algorithms used in graph partitioning, namely: graph coarsening and our diffusion-based method.

All the remapping algorithms that have been designed last year were meant to be easily parallelizable. The work of this year has been to derive and implement their parallel formulation. This is now the case, which completes this five year long work. These algorithms, which offer a quality similar to the one of the sequential algorithms, will be released in version 6.1 of Scotch .